package com.demo.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 每次重待排序的记录中选择最小的元素，放在已排好序的最后，知道全部记录排完
 * 简单选择排序
 * 树型选择排序
 * 堆排序
 */
public class SelectionSort {

    private static int[] getRandom() {
        int size = 10;
        int[] result = new int[size];
        for(int i=0;i<size;i++) {
            int rand = new Random().nextInt(size);
            result[i] = rand;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = getRandom();
        System.out.println("排序前:"+Arrays.toString(arr));
        simpleSelect(arr);
        System.out.println("排序后:"+Arrays.toString(arr));
    }

    /**
     * 通过n-i此比较，从n-i+1个记录中选择出最小的记录并和第i个记录交换
     *
     *
     * 平均:O(n^2)
     * 最好:O(n^2)
     * 最坏:O(n^2)
     * @param arr
     */
    public static void simpleSelect(int[] arr) {
        int len = arr.length;
        //排序N个排到N-1个 所有的顺序就会出来
        for (int i = 0; i < len - 1; i++) {
            int temp;
            //记录最小值的索引
            int index = i;
            for (int j = i + 1; j < len; j++) {
                if (arr[index] > arr[j]) {
                    index = j;
                }
            }
            //把获取最小值的位置和当前的索引i位置交换
            temp = arr[index];//记录最小值
            arr[index] = arr[i];//把当前i的值赋值给获取最小值的位置
            arr[i] = temp;//把最小值赋值给当前位置
        }
    }

    /**
     * 首先对n个记录的关键字进行两两比较，然后在其中[n/2](向上取整)个较小者之间在进行两两比较，知道选出最小关键子记录为止
     * 这个过程可以用一颗n个叶子节点的完全二叉树表示
     *
     *
     * @param arr
     */
    public static void treeSelect(int[] arr){

    }


}
